import datastructure.linklist.ListNode;

import java.util.LinkedList;
import java.util.List;

/**
 * @Author ZhangCuirong
 * @Date 2025/8/4 20:57
 * @description:
 */
public class Solution143 {
    public void reorderList(ListNode head) {
        List<ListNode> list = new LinkedList<>();
        ListNode p = head;
        while (p != null) {
            list.add(p);
            p = p.next;
        }
        int left = 0;
        int right = list.size() - 1;
        ListNode cur = new ListNode(-1);
        while (left < right) {
            cur.next = list.get(left);
            cur = cur.next;
            cur.next = list.get(right);
            cur = cur.next;
            left++;
            right--;
        }
        if (left == right){
            cur.next = list.get(left);
            cur = cur.next;
        }
        cur.next = null;
    }

    public static void main(String[] args) {
        int [] nums = {1,2,3,4,5};
        ListNode head = ListNode.arrayToList(nums);
        Solution143 solution = new Solution143();
        solution.reorderList(head);
        ListNode.printList(head);
    }

}
